package com.markus.code.剑指offer;

import org.jcp.xml.dsig.internal.dom.ApacheOctetStreamData;

import java.util.HashMap;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/31 13:22
 * todo: 重建二叉树
 */
public class BuildTree {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    private HashMap<Integer, Integer> indexMap;
    private int[] preorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length == 0 || preorder.length != inorder.length) {
            return null;
        }
        this.preorder = preorder;
        indexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i], i);
        }
        TreeNode node = buildCore(0, preorder.length - 1, 0, inorder.length - 1);
        return node;
    }

    private TreeNode buildCore(int preL, int preR, int inL, int inR) {
        if (preL > preR) {
            return null;
        }
        int rootValue = preorder[preL];
        TreeNode root = new TreeNode(rootValue);
        int index = indexMap.get(rootValue);
        root.left = buildCore(preL + 1, preL+index-inL, inL, index - 1);
        root.right = buildCore(preL+index-inL+1, preR, index + 1, inR);
        return root;
    }

    private void postOrder(TreeNode root) {
        if (root != null) {
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.val + " ");
        }
    }

    public static void main(String[] args) {
        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};
        BuildTree demo = new BuildTree();
        TreeNode tree = demo.buildTree(preorder, inorder);
        demo.postOrder(tree);
    }
}
